(defun range (start end &optional (step 1))
  (loop for i from start to end by step collect i)) 

(defun n-th-triangle-num (n)
  (/ (* n (1+ n)) 2))

;;; a. list of divisors that smaller than sqrt of num
;;; b. change the upper limit sqrt num to num in order to get all divisors including itself
;;;    refer a better solution at p21.lisp
(defun divisors-of (num)
  (remove-if-not
	(lambda (x) (= (mod num x) 0))
	(range 1 (floor (sqrt num)))))

(defun p12 (divisors-count)
  (do ((i 1 (1+ i)) (tn 1 (n-th-triangle-num i)))
	  ((>= (* (length (divisors-of tn)) 2) divisors-count) tn)
	  ))

;;; takes 118 seconds and GC time is 6 seconds
;(format t "~a~%" (time (p12 500)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(defun euler12 (&optional (divisors 500))
  (do* ((n 1 (1+ n)) (tn 1 (+ n tn)))
       ((> (num-divisors (prime-factor tn)) divisors) tn)))
 
""" Tau, function
    http://mathschallenge.net/index.php?section=faq&ref=number/number_of_divisors
"""
(defun num-divisors (lst)
  (reduce #'* (mapcar #'(lambda (i) (1+ (count i lst)))
                      (remove-duplicates lst))))
 
;;; more efficient than that in p3.lisp. why?
(defun prime-factor (n)
  (when (> n 1)
    (let ((limit (1+ (isqrt n))))
      (do ((i 2 (1+ i))) 
		  ((> i limit) (list n))
          (when (zerop (mod n i))
                (return-from prime-factor (cons i (prime-factor (/ n i)))))))))

;;; 6.4 seconds
(format t "~a~%" (time (euler12)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
